package com.hy.dp.subsequence;

public class DisjointLines {


    /**
     * 1035.不相交的线 （最长公共子序列）
     * 力扣题目链接
     *
     * 我们在两条独立的水平线上按给定的顺序写下 A 和 B 中的整数。
     *
     * 现在，我们可以绘制一些连接两个数字 A[i] 和 B[j] 的直线，只要 A[i] == B[j]，且我们绘制的直线不与任何其他连线（非水平线）相交。
     *
     * 以这种方法绘制线条，并返回我们可以绘制的最大连线数。
     *
     * 思路
     * 相信不少录友看到这道题目都没啥思路，我们来逐步分析一下。
     *
     * 绘制一些连接两个数字 A[i] 和 B[j] 的直线，只要 A[i] == B[j]，且直线不能相交！
     *
     * 直线不能相交，这就是说明在字符串A中 找到一个与字符串B相同的子序列，且这个子序列不能改变相对顺序，只要相对顺序不改变，链接相同数字的直线就不会相交。
     *
     * 拿示例一A = [1,4,2], B = [1,2,4]为例，相交情况如图：
     *
     * 其实也就是说A和B的最长公共子序列是[1,4]，长度为2。
     *
     * 这个公共子序列指的是相对顺序不变（即数字4在字符串A中数字1的后面，那么数字4也应该在字符串B数字1的后面）
     *
     * 这么分析完之后，大家可以发现：本题说是求绘制的最大连线数，其实就是求两个字符串的最长公共子序列的长度！
     *
     * 那么本题就和我们刚刚讲过的这道题目动态规划：1143.最长公共子序列就是一样一样的了。
     *
     * 一样到什么程度呢？ 把字符串名字改一下，其他代码都不用改，直接copy过来就行了。
     *
     * 其实本题就是求最长公共子序列的长度，介于我们刚刚讲过动态规划：1143.最长公共子序列，所以本题我就不再做动规五部曲分析了。
     *
     * 总结
     * 看到代码大家也可以发现其实就是求两个字符串的最长公共子序列，但如果没有做过1143.最长公共子序列，本题其实还有很有难度的。
     *
     * 这是Carl为什么要先讲1143.最长公共子序列再讲本题，大家会发现一个正确的刷题顺序对算法学习是非常重要的！
     *
     * 这也是Carl做了很多题目（包括ACM和力扣）才总结出来的规律，大家仔细体会一下哈。
     *
     *
     * @param nums1
     * @param nums2
     * @return
     */
    public static int disjointLines(int [] nums1,int [] nums2){
            int [][] dp = new int[nums1.length + 1][nums2.length +1];
        for (int i = 1; i <= nums1.length; i++) {
            for (int j = 1; j <= nums2.length; j++) {
                if (nums1[i - 1] == nums2[j - 1]){
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                }else {
                    dp[i][j] = Math.max(dp[i - 1][j],dp[i][j - 1]);
                }
            }
        }
        return dp[nums1.length][nums2.length];
    }


    public static void main(String[] args) {
        int [] nums1 = {1,2,4};
        int [] nums2 = {1,4,2};

        System.out.println("res: "+disjointLines(nums1,nums2));
    }
}
